class FPT

fixed-parameter tractable problems, FPT, 固定参数算法, para-P
#complexity_theory

Definition

fixed parameter tractable (FPT) problems, class of parameterized problems that can be solved in $f(k) \cdot n^{O(1)}$ time

Notes

also known as para-P (compare to P)
analogous to Karp reduction, there is also FPT-reduction

See also

PRAM model

References